# -*- coding: utf-8 -*-
# Created by zhangyanqi on 2018/4/23

"""
给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。
"""


# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x, l, r):
        self.val = x
        self.left = l
        self.right = r


class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
        left_deep = self.maxDepth(root.left)
        right_deep = self.maxDepth(root.right)
        if left_deep > right_deep:
            current_max_deep = left_deep + 1
        else:
            current_max_deep = right_deep + 1
        return current_max_deep


if __name__ == "__main__":
    node1 = TreeNode(10, None, None)
    node2 = TreeNode(20, None, None)
    node3 = TreeNode(10, node1, node2)

    s = Solution()
    depth = s.maxDepth(node3)
    print(depth)
